////////////////////////////////////////////////////////////////////// 
// libsrc/IntArray.cpp 
// (c) 2000-2008 Goncalo Abecasis
// 
// This file is distributed as part of the MaCH source code package   
// and may not be redistributed in any form, without prior written    
// permission from the author. Permission is granted for you to       
// modify this file for your own personal use, but modified versions  
// must retain this copyright notice and must not be distributed.     
// 
// Permission is granted for you to use this file to compile MaCH.    
// 
// All computer programs have bugs. Use this file at your own risk.   
// 
// Saturday April 12, 2008
// 
 
#include "IntArray.h"
#include "Error.h"
#include "Hash.h"
#include "Sort.h"

#include <string.h>

int IntArray::alloc = 4;

IntArray::IntArray(int start_size)
   {
   count = start_size;
   size = (count + alloc) / alloc * alloc;
   items = new int [size];
   }

IntArray::IntArray(const IntArray & source)
   {
   count = source.count;
   size = source.size;
   items = new int [size];

   for (int i = 0; i < count; i++)
      items[i] = source.items[i];
   }

IntArray::~IntArray()
   {
   delete [] items;
   }

void IntArray::Grow(int new_size)
   {
   if (new_size > size)
      {
      if ((new_size >> 1) >= size)
         size = (new_size + alloc) / alloc * alloc;
      else
         {
         size = alloc;
         while (size <= new_size)
            size *= 2;
         }

      int * new_items = new int [size];
      for (int i = 0; i < count; i++)
         new_items[i] = items[i];
      delete [] items;
      items = new_items;
      }
   }

int IntArray::Append(int value)
   {
   Grow(count + 1);
   items[count++] = value;
   return count;
   }

int IntArray::Append(const IntArray & rhs)
   {
   Grow(count + rhs.count);
   for (int i = 0; i < rhs.count; i++)
      items[count + i] = rhs.items[i];
   count += rhs.count;
   return count;
   }

void IntArray::Set(int value)
   {
   for (int i = 0; i < count; i++)
      items[i] = value;
   }

void IntArray::SetSequence(int start, int increment)
   {
   for (int i = 0; i < count; i++, start += increment)
      items[i] = start;
   }

int IntArray::Delete(int index)
   {
   count--;
   if (count - index)
      memmove(items + index, items + index + 1, sizeof(int) * (count - index));
   return count;
   }

void IntArray::InsertAt(int index, int value)
   {
   Grow(count + 1);
   if (count - index)
      memmove(items + index + 1, items + index, sizeof(int) * (count - index));
   items[index] = value;
   count++;
   }

IntArray & IntArray::operator = (const IntArray & rhs)
   {
   Grow(rhs.count);
   count = rhs.count;
   for (int i = 0; i < count; i++)
      items[i] = rhs.items[i];
   return *this;
   }

int IntArray::Sum(int start, int end) const
   {
   int result = 0;

   for (int i = start; i <= end; i++)
      result += items[i];

   return result;
   }

int IntArray::Max(int start, int end) const
   {
   if (start >= count) return 0;

   int result = items[start];

   for (int i = start + 1; i <= end; i++)
      if (result < items[i])
         result = items[i];

   return result;
   }

int IntArray::Min(int start, int end) const
   {
   if (start >= count) return 0;

   int result = items[start];

   for (int i = start + 1; i <= end; i++)
      if (result > items[i])
         result = items[i];

   return result;
   }

int IntArray::Find(int value) const
   {
   for (int i = 0; i < count; i++)
      if (value == items[i])
         return i;
   return -1;
   }

int IntArray::BinarySearch(int value) const
   {
   int start = 0;
   int stop = count - 1;

   while (start <= stop)
      {
      int mid = (start + stop) / 2;

      if (items[mid] == value)
         return mid;

      if (items[mid] > value)
         stop = mid - 1;
      else
         start = mid + 1;
      }

   return -1;
   }

void IntArray::Zero()
   {
   for (int i = 0; i < count; i++)
      items[i] = 0;
   }

int IntArray::Compare(int * a, int * b)
   { return *a - *b; }

void IntArray::Sort()
   {
   QuickSort(items, count, sizeof(int), COMPAREFUNC Compare);
   }

void IntArray::Sort(IntArray & freeRider)
   {
   QuickSort2(items, freeRider.items, count, sizeof(int), COMPAREFUNC Compare);
   }


void IntArray::Reverse()
   {
   for (int i = 0, j = count - 1; i < j; i++, j--)
      Swap(i, j);
   }

int IntArray::CountIfGreater(int threshold) const
   {
   int result = 0;

   for (int i = 0; i < count; i++)
      if (items[i] > threshold)
         result++;

   return result;
   }

int IntArray::CountIfGreaterOrEqual(int treshold) const
   {
   int result = 0;

   for (int i = 0; i < count; i++)
      if (items[i] >= treshold)
         result++;

   return result;
   }

void IntArray::Add(int term)
   {
   for (int i = 0; i < count; i++)
      items[i] += term;
   }

void IntArray::Multiply(int factor)
   {
   for (int i = 0; i < count; i++)
      items[i] *= factor;
   }

void IntArray::Divide(int denominator)
   {
   for (int i = 0; i < count; i++)
      items[i] /= denominator;
   }
   
void IntArray::Stack(const IntArray & a)
   {
   int end = count;

   Dimension(count + a.count);

   for (int i = 0; i < a.count; i++)
      items[i + end] = a[i];
   }

bool IntArray::operator == (const IntArray & rhs) const
   {
   if (count != rhs.count)
      return false;

   for (int i = 0; i < rhs.count; i++)
      if (items[i] != rhs.items[i])
         return false;

   return true;
   }

bool IntArray::operator != (const IntArray & rhs) const
   {
   return !(*this == rhs);
   }

// Check if all values are in ascending or descending order
//

bool IntArray::isAscending()
   {
   for (int i = 1; i < count; i++)
      if (items[i] < items[i - 1])
         return false;
   return true;
   }

bool IntArray::isDescending()
   {
   for (int i = 1; i < count; i++)
      if (items[i] > items[i - 1])
         return false;
   return true;
   }

void IntArray::Add(const IntArray & v)
   {
   if (Length() != v.Length())
      error("IntArray::Add - vectors have different lengths\n"
            "IntArrays     - Left[%d] += Right[%d] ",
            Length(), v.Length());

   for (int i = 0; i < Length(); i++)
      items[i] += v[i];
   }

int IntArray::InnerProduct(IntArray & v)
   {
   if (Length() != v.Length())
      error("IntArray::InnerProduct - vectors have different dimensions\n"
            "IntArrays              - Left[%d] * Right[%d] ",
            Length(), v.Length());

   int sum = 0;
   for (int i = 0; i < Length(); i++)
      sum += items[i] * v[i];

   return sum;
   }

void IntArray::Swap(IntArray & rhs)
   {
   int * temp = rhs.items;
   rhs.items = items;
   items = temp;

   int swap = rhs.count;
   rhs.count = count;
   count = swap;

   swap = rhs.size;
   rhs.size = size;
   size = swap;
   }

void IntArray::Print(FILE * output)
   {
   Print(output, "Array of Integers");
   }

void IntArray::Print(FILE * output, const char * label)
   {
   fprintf(output, "%s [%d elements]: ", label, count);

   for (int i = 0; i < count; i++)
      fprintf(output, "%d ", items[i]);

   fprintf(output, "\n");
   }

void IntArray::PushIfNew(int value)
   {
   for (int i = 0; i < count; i++)
      if (items[i] == value)
         return;

   Push(value);
   }

int IntArray::Product()
   {
   int product = 1;

   for (int i = 0; i < count; i++)
      product *= items[i];

   return product;
   }

double IntArray::DoubleProduct()
   {
   double product = 1.0;

   for (int i = 0; i < count; i++)
      product *= items[i];

   return product;
   }

int IntArray::Hash(int initval)
   {
   return hash((unsigned char *) items, sizeof(int) * count, initval);
   }
 
